public class BitUtils {
    private final static int[] BYTE_BIT_COUNT = {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
    };

    public static int countBits(int n) {
        return BYTE_BIT_COUNT[  n & 0xff ]
             + BYTE_BIT_COUNT[ (n >>>  8) & 0xff ]
             + BYTE_BIT_COUNT[ (n >>> 16) & 0xff ]
             + BYTE_BIT_COUNT[  n >>> 24 ];
    }

    public static int countBits(long n) {
        return BYTE_BIT_COUNT[ (int)  (n & 0xff) ]
             + BYTE_BIT_COUNT[ (int) ((n >>>  8) & 0xff) ]
             + BYTE_BIT_COUNT[ (int) ((n >>> 16) & 0xff) ]
             + BYTE_BIT_COUNT[ (int) ((n >>> 24) & 0xff) ]
             + BYTE_BIT_COUNT[ (int) ((n >>> 32) & 0xff) ]
             + BYTE_BIT_COUNT[ (int) ((n >>> 40) & 0xff) ]
             + BYTE_BIT_COUNT[ (int) ((n >>> 48) & 0xff) ]
             + BYTE_BIT_COUNT[ (int)  (n >>> 56) ];
    }

    private final static int SHIFT[] = {1, 2, 4, 8, 16};
    private final static int MASK[] = {0x55555555, 0x33333333, 0x0F0F0F0F,
                                       0x00FF00FF, 0x0000FFFF};

    public static int countBitsParallel(int n) {
        for (int i = 0; i < SHIFT.length; i++) {
            n = (n & MASK[i]) + ((n >>> SHIFT[i]) & MASK[i]);
        }

        return n;
    }

    private final static int LSHIFT[] = {1, 2, 4, 8, 16, 32};
    private final static long LMASK[] = {
        0x5555555555555555L, 0x3333333333333333L, 0x0F0F0F0F0F0F0F0FL,
        0x00FF00FF00FF00FFL, 0x0000FFFF0000FFFFL, 0x00000000FFFFFFFFL};

    public static int countBitsParallel(long n) {
        for (int i = 0; i < LSHIFT.length; i++) {
            n = (n & LMASK[i]) + ((n >>> LSHIFT[i]) & LMASK[i]);
        }

        return (int) n;
    }

    private final static int MASK1 = 0x55555555;
    private final static int MASK2 = 0x33333333;
    private final static int MASK4 = 0x0F0F0F0F;
    private final static int MASK8 = 0x00FF00FF;
    private final static int MASK16 = 0x0000FFFF;

    public static int countBitsParallel2(int n) {
        n = (n & MASK1)  + ((n >>> 1)  & MASK1);
        n = (n & MASK2)  + ((n >>> 2)  & MASK2);
        n = (n & MASK4)  + ((n >>> 4)  & MASK4);
        n = (n & MASK8)  + ((n >>> 8)  & MASK8);
        n = (n & MASK16) + ((n >>> 16) & MASK16);

        return n;
    }

    private final static long LMASK1 = 0x5555555555555555L;
    private final static long LMASK2 = 0x3333333333333333L;
    private final static long LMASK4 = 0x0F0F0F0F0F0F0F0FL;
    private final static long LMASK8 = 0x00FF00FF00FF00FFL;
    private final static long LMASK16 = 0x0000FFFF0000FFFFL;
    private final static long LMASK32 = 0x00000000FFFFFFFFL;

    public static int countBitsParallel2(long n) {
        n = (n & LMASK1)  + ((n >>> 1)  & LMASK1);
        n = (n & LMASK2)  + ((n >>> 2)  & LMASK2);
        n = (n & LMASK4)  + ((n >>> 4)  & LMASK4);
        n = (n & LMASK8)  + ((n >>> 8)  & LMASK8);
        n = (n & LMASK16) + ((n >>> 16) & LMASK16);
        n = (n & LMASK32) + ((n >>> 32) & LMASK32);

        return (int) n;
    }

    public static int floorLog2(int i) {
        i |= (i >> 1);
        i |= (i >> 2);
        i |= (i >> 4);
        i |= (i >> 8);
        i |= (i >> 16);

        return countBits(i) - 1;
    }

    /**
     * Compute the floor of the log base 2 function. Since the log function is
     * only defined for positive values, this function returns a negative value
     * ({@link Integer#MIN_VALUE}) if i <= 0.
     *
     * @return floor of log base 2
     * @see <a href="http://aggregate.org/MAGIC/#Log2 of an Integer"
     *     >Implementation adapted from The Aggregate Magic Algorithms</a>
     */
    public static int floorLog2b(int i)
    {
        if (i <= 0)
        {
            return Integer.MIN_VALUE;
        }

        return highestBitSet(i) - 1;
    }

    /**
     * Compute the position of the highest bit that is set for the specified
     * {@code int} value. The position is starting from 1 for the LSB and goes
     * up to 32 for the MSB. The function will return 0 for an argument 0 and 32
     * for any negative argument.
     * <p>
     * The semantics of this function is intentionally chosen to be the same as
     * the semantics for the Mitrion-C function, with the exception that this
     * function is defined for negative values (even if there isn't much point
     * in using it for negative values), while highestbitset in Mitrion-C is
     * only defined for the types {@code uint} and {@code bits}.
     * </p>
     *
     * @return the highest bit set starting at 1
     */
    public static int highestBitSet(int i)
    {
        // Put the highest one bit into all the less significant bits
        i |= (i >> 1);
        i |= (i >> 2);
        i |= (i >> 4);
        i |= (i >> 8);
        i |= (i >> 16);

        return Integer.bitCount(i);
    }
}
